1. Field of the Invention
The present invention relates to a technique for image processing. In particular, this invention relates to an image processing apparatus and methods that can rotate, enlarge, reduce, clip and overlap images at low cost and high speed.
2. Discussion of the Related Art
Generally, image processing can be largely divided into two types. One type is geometrical processing which changes the position of the pixels. The other type is pixel value processing which changes the value of the pixels. Examples of geometrical processing are affine transformation, such as rotation, enlargement or reduction of images, and clipping or overlapping of images which cut out pixels. Pixel value processing includes color correction and filter processing.
Among these types of image processing, the rotating process differs substantially from the others. In general, image data is processed in the order of the raster scan, and the result is output in that order as well. On the other hand, when rotating images, the order of input and output of data differs at the source, or input side, and the destination, or output side.
When data is input from the source side according to the raster scan order and is rotated, it is written diagonally on the destination side. In this case, random access of image data is necessary at the destination side. This is called a sequential transform method. When image data is sent so that it appears in the raster scan order at the destination side, random access is necessary at the source side. This is known as an inverse transform method.
In both methods, random access is necessary either on the source side or the destination side. To make random access possible, page memory is used in existing technologies. In the case of the sequential transform method, the rotated image is created in the page memory of the destination side. On the other hand, in the inverse transform method, all images are first written in the page memory and then rotated. Methods that can reduce the amount of time needed for sending image data and for calculating coordinates have been suggested hitherto based on these two methods.
One of these methods is disclosed by Japanese Laid-Open Patent Application No.61-161576. This method aims to increase the speed of the image rotation process by dividing the images into blocks and processing them locally.
FIG. 16 is a block diagram illustrating this method. The image input unit 10 stores input image data 200 in a page memory of the source side 49. The inverse transform coordinate calculating unit 29 calculates the source side coordinate by inversely transforming the center pixel of the local data at the destination side. This coordinate is then output as the inverse transform coordinate 229.
The page memory reading unit 48 sends the source side address of the local data 228 to the source side page memory 49. The inverse transform coordinate 229 is the center of the source side address of the local data 228. The source side page memory 49 stores input image data 200 and sends local data 230 to local data transform unit 51 as indicated by the source side address 228. The local data 230 is, for example, a 3xc3x973 pixel block data.
The local data transform unit 51 reads local data 230 and performs such transform processing as rotation, enlargement or reduction according to the transforming information 231 stored in transforming ROM 52. The local transform unit 51 then outputs the transformed local data 240 to the destination side page memory 79. Page memory writing unit 78 sends the destination side address 269 to the destination side page memory 79, which corresponds to inverse transform coordinate 229. The destination side page memory 79 stores the transformed local data 240 and then sends the local data 270 to image output unit 80 according to the destination side address 269. Image output unit 80 then outputs the output image.
FIG. 17 describes a process in which the rotating process of an image is separated into local rotation and global rotation based on the above method. When local data 400 is rotated around pixel 420, which is the center of rotation, it becomes local data 430. However, since pixels must be aligned either horizontally or vertically, the actual object of the rotation process is to obtain post-rotation local data 450 and its coordinate. In this method, the post-rotation local data 450 is attained by locally rotating local data 430 around post-rotation center pixel 440. According to this method, by tabulating the destination coordinate within local data correspondent to rotation angle xcex1 and storing the table in ROM, there is no need to calculate coordinates for every local data since the processing is uniform for all local data. The post-rotation center pixel 440 can be calculated for each local data from the pre-rotation center pixel 410, center pixel 420 and rotation angle xcex1.
As can be seen from the above, the rotation process of this method is characterized by two separate processes: local processing based on transforming ROM 52, and global processing to obtain the address of the local data at its destination. The local processing is simplified enough to be performed at high speed by hardware, and the global processing can reduce the number of calculations. The problem with this method, however, is the high cost of the apparatus as a whole. Page memories are generally very expensive and this method assumes the need for two page memories.
The method explained hereafter reduces the cost of the apparatus by eliminating the need for page memories. This method is used in the inventions of Japanese Laid-Open Patent Applications Nos.62-140175 and 62-20074. In the first method, the rotating process is divided into local processing and global processing. When performing merely local processing, only the memory enough to store local data is needed. The second method eliminates global processing by using only a low-capacity buffer memory and performing the reading process many times across horizontal lines of data. FIG. 18 is a block diagram illustrating this method. The parts_that perform the same function as in FIG. 16 have the same numbers and are therefore, not explained here in repetition.
The buffer reading unit 46 sends to the reading buffer 47 the source side address 227 of local data, the center of which is the inverse transform coordinate 229. The reading buffer 47 stores the input image data 200 in the order of the raster scan and then sends local data 230 to the local data transforming unit 51 according to the source side address information 227. The buffer writing unit 76 sends to writing buffer 77 the destination side address 26 which corresponds to the inverse transform coordinate 229. The writing buffer 77 stores the transformed local data 240, and then sends output image data 270 to the image output unit 80 according to the destination side address 268.
In the above method, the smaller the reading buffer 47, the lower the cost. Reading buffer 47 can be formed when there is enough capacity to store the number of lines needed when rotating local data at least forty-five degrees.
FIG. 19 shows the flow of local data((1)xcx9c(6)) from image input to image output. As shown in FIG. 19:
(1) The inverse transform coordinate (Xsrc, Ysrc), which corresponds to the center (Xdes, Ydes) of the local data, is calculated. The input image data is divided into blocks with regard to the coordinates of the destination side.
(2) The local data, the center of which is the inverse transform coordinate, is read and stored in the reading buffer 47. In performing this process, speedy reading by random access is not possible when low-priced hard disks are used. In such a case, all image data comprising the line including the local data in question are read.
(3) The local data, the center of which is the inverse transform coordinate, is read out from the reading buffer 47.
(4) The local data which has been read out in (3) is processed according to the transform ROM 52. Such processes include rotation, enlargement, and reduction.
(5) The processed local data is written in the writing buffer 77 according to the (Xdes, Ydes) coordinate mentioned in (1).
(6) The image is output once all of the image data are ready in the writing buffer 77.
The reading process (2) is performed so that the data appears in the order of the raster scan at the destination side. This means that at the source side, the reading process is performed many times across the same horizontal lines of data. It is necessary to read the same line a number of times since the reading buffer 47 of this method is presupposed to be small.
It is also possible to perform this method by the sequential transform method. This way, the reading process (2) only needs to be performed once. In this case, however, the process load is generally heavier compared to the reverse transform method since there is a need for a mechanism to rearrange the output image.
Using this method, it is possible to reduce the total cost because small capacity buffers for input and output are used instead of expensive page memories. However, since it is necessary to repeatedly read the same image at the source side, the speed of processing is very slow.
The present invention includes an image inputting element that sends input image data into a first band data storing element line by line in the order of the raster scan. An address control element sends source side address information to the first band data storing element and destination side address information to a transformed data storing element. The first band storing element outputs local data indicated by the source side address information to a local data transforming element which performs the rotating, enlarging and/or reducing of the image data.
The local data transforming element outputs the transformed local data to the transformed data storing element. The transformed local data storing element stores the transformed local data and outputs the transformed local data indicated by the destination side address information received from the address control element. The data output from the transformed local data storing element is stored in a second band data storing element. The second band data storing element outputs the stored transformed local data to an outputting element as output image data from which a transformed image may be reconstructed.
An aspect of the present invention is that the first and second band data storing elements may be ring buffers or double buffers. Another aspect is that the processing of the input image data may be performed in macro blocks comprised of two or more local data.
In another embodiment of the present invention, the transformed local data storing element further includes an image compressing unit and a compressed data storing unit. The image compressing unit compresses the transformed local data using at least one of a discrete cosine transform, a discrete Fourier transform, a discrete sine transform, a lapped orthogonal transform, a Hadamard transform, a Wavelet transform and a sub-band coding. The data stored in the compressed data storing unit is data compressed by the image compressing unit using at least one of the above transforms. Additionally, the data stored in the second band buffer may be either compressed data or uncompressed data.
In another embodiment of the present invention, the address control unit includes an address list generating unit that generates an address list showing the relationship between the coordinates of the input image data and the coordinates of the output image data. This embodiment also includes an address list sorting unit that rearranges the address list according to a processing order of the input image data.
In yet another embodiment of the present invention, the address control unit includes at least one of a clipping information generating unit and an overlapping information generating unit that outputs at least one of clipping information and overlapping information. In this embodiment, the address list generating unit generates the address list according to a processing order of the output image data based on at least one of the clipping information and the overlapping information.
In the method of the present invention, image data is input and each local data which constitute the image data is transformed into transformed local data by performing a predetermined image processing upon the local data. The transformed data is stored and read in the order that it is to be output. The transformed local data is rearranged into portions of an output image. The rearranged transformed local data is then output as an output image.
The method further includes sending the input image data to a first band storing element line by line in the order of the raster scan; receiving source side address information and destination side address information; transforming the local data indicated by the source side address information into transformed local data by performing at least one of rotating, enlarging and reducing the local data; storing the transformed local data; outputting the transformed local data indicated by the destination side address information to a second band storing element; and outputting the stored transformed local data as output image data from which a transformed image is reconstructed.
An aspect of the method is that the first and second band data storing elements may be ring buffers or double buffers. Another aspect is that the processing of the input image data may be performed in macro blocks comprised of two or more local data.
In another embodiment of the present invention, the method further includes compressing the transformed local data using at least one of a discrete cosine transform, a discrete Fourier transform, a discrete sine transform, a lapped orthogonal transform, a Hadamard transform, a Wavelet transform and a sub-band coding. In another embodiment of the present invention, the method includes generating an address list showing the relationship between the coordinates of the input image data and the coordinates of the output image data. This embodiment also includes rearranging the address list according to a processing order of the input image data.
In yet another embodiment of the present invention, the method includes generating at least one of clipping information and overlapping information. In this embodiment, the address list is generated according to a processing order of the output image data based on at least one of the clipping information and the overlapping information.